package com.chenyi.leetcode.editor.cn;

/**
 * [35]搜索插入位置
 *
 * @author by chenyi
 * @className SearchInsertPosition
 * @date 2022-06-21 00:13:11
 */
public class SearchInsertPosition {
    public static void main(String[] args) {
        Solution solution = new SearchInsertPosition().new Solution();
        System.out.println(solution.searchInsert1(new int[]{1, 3, 5, 6}, 7));
    }

    @SuppressWarnings("AlibabaCommentsMustBeJavadocFormat")
            //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        /** 线型查找
         * @param nums
         * @param target
         * @return
         */
        public int searchInsert(int[] nums, int target) {
            int index = -1;
            for (int i = 0; i < nums.length; i++) {
                if (target <= nums[i]) {
                    index = i;
                    break;
                }
            }
            if (index == -1) {
                return index = nums.length;
            }
            return index;
        }

        /**
         * 二分查找
         * @param nums
         * @param target
         * @return
         */
        public int searchInsert1(int[] nums, int target) {
            int left = 0;
            int right = nums.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (target < nums[mid]) {
                    right = mid - 1;
                } else if (target == nums[mid]){
                    return mid;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
